/**
 * 最长的有效括号
 *
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 * 示例 1：
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 *
 * 示例 2：
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 *
 * 示例 3：
 * 输入：s = ""
 * 输出：0
 *
 * 提示：
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 */

import java.util.Stack;

/**
 * 1. 超时方法, 虽然我已经用了优化了, 但还是会超时, 用的最傻的方法, 就是暴力,
 * 我们一个一个的列举, 把所有的可能列举出来, 然后使用栈判断是否为有效括号, 虽然
 * 我是里面的循环是从尾巴向前遍历, 只要遇到了有效括号就立即退出, 但是还是会超时,
 * 大概是判断是否为有效扩括号的时候超时的吧
 * 时间复杂度 : O(n^3)
 * 空间复杂度 : O(n)
 *
 * 2. 因为上面那种方法超时了 所以我们另想一种方法来优化, 我们从第一个位置开始, 开始一直计算
 * 有效的括号, 存入'('的下标, 利用先进后出我们完全可以求出最长的有效长度, 我们要是遇到 '('
 * 直接下标入栈就可以了, 要是遇到 ')', 出栈匹配, 并且用这个下标减去栈顶元素的下标(这个是和他匹配的元素的下标)
 * 注意这里我们可能会想当然, 因为我们要是 ()() 这样出现字符的话, 我们每次只能取到 () 的长度, 所以我们
 * 需要更加细节一点, 就比如我们我将他们连起来, 就要是到 第一个 ()前的下标, 后续拿匹配的 )下标减去前面的
 * 下标就可以了, 所以我们要先出栈, 然后在取栈顶元素, 让他们相减, 所以我们遇到 ) 且栈为空的时候, 也要出栈
 * 且更新栈顶下标为他的下标, 还有一个细节, 就是一开始的位置怎么解决, 要是一开始就是 ( 我们根本没有遇到 ) 加入
 * 其下标的能力, 所以我们要在栈中加个 -1, 这样我们在 一开始遇到 ) 也不用判断站是否为空了, 因为不可能为空
 * 这时候得到的长度去更新最长的长度, 后面我们肯定会遇到第一个位置结束的时候, 这个时候我们会遇到两种情况,
 * 1. '(' 这里说明我们从第一位开始的有效括号是还没有结束的 , 继续入栈
 * 2. ')' 这里说明我们一开始位置的有效括号已经结束了, 当然这个值被我们存储着, 我们得重新开始计算长度了
 * 当然我们后面要是结束的时候栈内还有 '(', 就说名这几个 '(' 都是多余的
 * 这种方法只需要遍历一遍字符数组就可以了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 *
 * 3. 看到题目的要求, 我第一反应是用动态规划来写, 但是就是想不到状态表示, 我们看
 * 题目是要求最长的长度, 所以就往这上面靠, 试着定义dp[i] : 以 i 结尾的字符串中最长的有效括号长度
 * 结尾我们会遇到两种字符
 * ) : 遇到这个我们就判断下前面的字符 , 要是 ( : dp[i] = dp[i - 2] + 2,
 *                                要是 ) : 这里要注意了, 这个 dp[i]结尾的可能是是有对应的有效括号的,
 *                                我们从这一点出发可以发现, 有效括号前面肯定是没有连续的()这样的组合了,
 *                                也就是我们后面的 ) 想要匹配上就必须要求前面的是 ( , 这样
 *                                dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
 *                                这里的dp[i - 1]是前面的有效括号, 因为后面的 ) 还是和前面连起来的,
 *                                所以我们在将前面一个位置和后面一个位置减去, 再加上他们匹配的两个括号
 *                                这里我们肯定会有一个疑问, 就是为啥前面加上就不用管了呢, 为啥前面就不会再有 ()
 *                                这里我们来举个列子说明下
 *                                我们现在  () (....) ) , 要是前面有这样的就会被 归为dp[i - 1]
 *                                dp[i - 1] 出现的条件一定是前面已经没有有效组合了 () ) (...)  ) 或者 () ( (...) )
 *                                第一个前面是右有效组合但是已经加不进去了, 因为值 ) 结尾, 所以中间是断了的了, 后面的是可以和前面
 *                                有效组合连起来, 所以我们要加上 dp[i - dp[i - 1] - 2], 前面要是有紧贴的有效括号组合, 是拆不开的
 *                                现在懂了吗!!!!!!
 * ( : 遇到这个也就是直接 dp[i] = 0
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {

    // 1. 暴力解法
    public int longestValidParentheses1(String s) {

        // 转化成字符数组
        char[] nums = s.toCharArray();

        // 求其长度
        int n = s.length();

        // 返回的最长有效括号长度
        int maxLen = 0;

        // 外围第一层循环
        for (int i = 0; i < n; i++) {

            // 这里要是开头是 ')' 直接下一层
            if (nums[i] == ')') {
                continue;
            }

            // 这里优化下, 要是 后面的长度都没有 maxLen长直接 break
            if (maxLen > n - i) {
                break;
            }

            // 第二层循环
            // 这里了我们从后面向前遍历, 这样如果找到了一个符合要求的
            // 组合, 那么一定是这层循环中最长的有效括号, 直接break 就可以了
            for (int j = n - 1; j >= i + 1; j--) {

                // 要是结尾时 '(' , 直接 continue
                if (nums[j] == '(') {
                    continue;
                }

                // 判断是否为有效括号
                if (isValid(nums, i , j)) {

                    // 是的话更新最长长度, 并 break
                    maxLen = Math.max(maxLen, j - i + 1);
                    break;
                }
            }
        }

        // 返回最长长度
        return maxLen;
    }

    /**
     * 判断给定的字符数组是否为有效括号
     *
     * @param nums 字符数组
     * @param i    起始位置
     * @param j    结束位置
     * @return
     */
    private boolean isValid(char[] nums, int i, int j) {

        // 栈
        Stack<Character> stack = new Stack<>();

        for (int k = i; k <= j; k++) {

            // 判断字符是 '(', 还是 ')'
            if (nums[k] == '(') {

                // '(' 入栈
                stack.push(nums[k]);
            } else {

                // ')' 栈
                // 先看下栈中是否有元素, 要是没有, 自然就出不了
                int size = stack.size();
                if (size == 0) {
                    return false;
                }

                // 出栈
                stack.pop();
            }
        }

        // 要是循环结束后, 栈中还剩下元素, 也是不符合要求的
        if (stack.isEmpty()) {

            // 空栈符合要求
            return true;
        }
        return false;
    }

    // *******************************************************************
    // 2.遍历一遍
    public int longestValidParentheses2(String s) {

        // 转化成字符数组
        char[] nums = s.toCharArray();

        // 求其长度
        int n = s.length();

        // 返回的最长有效括号长度
        int maxLen = 0;

        // 栈
        Stack<Integer> stack = new Stack<>();

        // 初始话元素
        stack.push(-1);

        for (int i = 0; i < n; i++) {
            if (nums[i] == '(') {
                stack.push(i);
            } else {

                // 先出栈一个元素, 为了有效的括号能连接起来
                stack.pop();

                // 判断栈是否为空, 要是空了要加入此次 ')' 的下标作为初始化下标
                if (stack.isEmpty()) {

                    // 入栈
                    stack.push(i);
                } else {

                    // 拿栈顶元素
                    int j = stack.peek();

                    // 这里也不用加一, 因为存的就是前面一个数的下标
                    maxLen = Math.max(maxLen, i - j);
                }
            }
        }
        return maxLen;
    }

    // ****************************************************************
    // 3. 动态规划
    public int longestValidParentheses(String s) {

        // 转化成字符数组
        char[] nums = s.toCharArray();

        // 求其长度
        int n = s.length();

        // 返回的最长有效括号长度
        int maxLen = 0;

        // 不用预留位置了, 这里我们在会越界的地方加判断条件 也不用初始化, 因为初始化为0
        int[] dp = new int[n];

        // 自带第一个数, 所以不用判断第一个数
        for (int i = 1; i < n; i++) {

            // 判断该括号是啥括号
            if (nums[i] == '(') {

                // 左括号结尾直接是无效
                dp[i] = 0;

            } else {

                // 右括号结尾

                // 这里我们需要知道他的前面一个是什么扩阿訇
                if (nums[i - 1] == '(') {

                    // 要是 左括号, 先天就可以和该括号组合成一对
                    dp[i] = 2;

                    // 在判断前面是否还有括号, 要是有括号 把以这个结尾的有效括号加进来
                    if (i >= 2) {
                        dp[i] += dp[i - 2];
                    }

                } else {

                    // 要是前面是右括号
                    // 我们要判断前面有效括号结束后前面是否还有左括号
                    // 这里解释过了, 有效组合无法被该括号插足, 要是前面直接没有要以他结尾的有效扩好, 在加上一个括号
                    // 也没有用, 但前面有有效括号, 我们就要判断有效括号结束后前面是啥括号了, 要是没越界, 前面还是
                    // ( 就可以在这个有效括号的基础上加上二, 要是去掉这个加上的括号前面还有有效括号可以来连起来,
                    // 我们继续加起来
                    // ) 这里就直接结束了, 因为前面不可能留着 ( 和你匹配, 要是有 ( 会和这个 ) 匹配, 加入前面那个有效括号的
                    // 组合, 不会留到 最后的) 匹配, 要是你还咱还觉的 (( ), 这样的可能得话, ( (), 这里有效的括号会给那个组合
                    // 而 会剩下 ( ,就会回到前面讨论 ( 个的时候了
                    if (i - dp[i - 1] - 1 >= 0 && nums[i - dp[i - 1] - 1] == '(') {

                        // 要是 ( 加上有效括号的组合, 加上匹配的2
                        dp[i] = dp[i - 1] + 2;

                        // 这里要判断下是否前面还有括号, 不然会越界
                        if (i - dp[i - 1] - 2 >= 0) {

                            // 加上前面去掉 ( 这个妨碍后可以连起来的有效括号组合
                            dp[i] += dp[i - dp[i - 1] - 2];
                        }
                    }
                }
            }

            // 每次循环更新一次最长的长度
            maxLen = Math.max(maxLen, dp[i]);
        }

        // 返回最长有效括号
        return maxLen;
    }


    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        String s = "(()";
        System.out.println(test.isValid(s.toCharArray(), 0, s.length() - 1));
        System.out.println(test.longestValidParentheses(s));
    }
}